1. Field
Embodiments of the invention relate to the field of networking; and more specifically, to optical networks.
2. Background
Generalized Multiprotocol Label Switching (GMPLS) [RFC3471] extends the Multiprotocol Label Switching (MPLS) architecture [RFC3031] to encompass time-division (e.g., Synchronous Optical Network and Synchronous Digital Hierarchy, SONET/SDH), wavelength (optical lambdas) and spatial switching (e.g., incoming port or fiber to outgoing port or fiber).
GMPLS extends MPLS to include network devices whose forwarding plane recognizes neither packet, nor cell boundaries, and therefore, can't forward data based on the information carried in either packet or cell headers. Specifically, such network devices include devices where the forwarding decision is based on time slots (TDM), wavelengths (lambda), or physical (fiber) ports. GMPLS supports uni-directional label switched paths (LSPs) and bi-directional LSPs (For bi-directional LSPs, the term “initiator” is used to refer to a node that starts the establishment of an LSP and the term “terminator” is used to refer to the node that is the target of the LSP; Note that for bi-directional LSPs, there is only one “initiator” and one “terminator”) and a special case of Lambda switching, called Waveband switching (A waveband represents a set of contiguous wavelengths which can be switched together to a new waveband; The Waveband Label is defined to support this special case; Waveband switching naturally introduces another level of label hierarchy; As far as the GMPLS protocols are concerned there is little difference between a waveband label and a wavelength label.).
To deal with the widening scope of MPLS into the optical and time domains, there are several new forms of “label.” These new forms of labels are collectively referred to as “generalized labels.” A generalized label contains enough information to allow the receiving node to program its switch fabric, regardless of the type of this switch fabric, such that the ingress and egress segments of the path are properly joined. The Generalized Label extends the traditional label by allowing the representation of not only labels which travel in-band with associated data packets, but also out-of-band labels which identify time-slots, wavelengths, or space division multiplexed positions. For example, the Generalized Label may carry a label that represents (a) a single fiber in a bundle of fibers, (b) a single waveband within fiber, (c) a single wavelength within a waveband (or fiber), or (d) a set of time-slots within a wavelength (or fiber). It may also carry a label that represents a generic MPLS label, a Frame Relay label, or an ATM label (VCI/VPI).
Thus, GMPLS forms label switched paths (LSPs) through the network. Examples of two signaling protocols available to set up LSPs across a network are the Resource Reservation Protocol (RSVP) and the label distribution protocol (LDP).
Optical Networks
An optical network is a collection of optical network devices interconnected by links made up of optical fibers. Thus, an optical network is a network in which the physical layer technology is fiber-optic cable. Cable trunks can be interconnected with optical cross-connects (OXCs), and signals can be added and dropped at optical add/drop multiplexers (OADMs). The optical network devices that allow traffic to enter and/or exit the optical network are referred to as access nodes. Each optical link interconnects two optical network devices and typically includes an optical fiber to carry traffic in each direction. There may be multiple optical links between two optical network devices.
A given fiber can carry multiple communication channels simultaneously through a technique called wavelength division multiplexing (WDM). When implementing WDM, each of multiple carrier wavelengths (or, equivalently, frequencies or colors) is used to provide an independent communication channel. Thus, a single fiber looks like multiple virtual fibers, with each virtual fiber carrying a different data stream. Each of these data streams may be a single data flow, or may be multiple logical data flows (such logical data flows may be distinguished by a variety of technologies—e.g., time slots, virtual partitions (e.g., tunnels), etc.) Each of the wavelengths used for these channels is often referred to as a lambda.
A lightpath is the route through one or more concatenated links taken by a particular light signal as it enters the network at the ingress node (also referred to as the source node) to where it is removed from the network at the egress node (also referred to as the destination node), as well as the set of one or more lambdas used to carry the optical signal. A lightpath thus consists of the physical fiber links between the ingress and egress nodes as well as the optical switching that occurs at any pass-through nodes (also referred to as intermediate nodes) for that lightpath. It would also include any wavelength conversion device(s) that may be present to realize the required connectivity. A lightpath for which wavelength conversion is not performed is referred to as a conversion free lightpath and comprises a single lambda and a path (the series of optical nodes (and, of course, the interconnecting links) through which traffic is carried with that set of lambdas); A lightpath for which wavelength conversion is performed is comprises multiple lambdas and a path. An optical circuit is the logical pairing of lightpaths between two nodes where at least one of the lightpaths is traveling in the opposite direction so as to allow bi-directional communication between the two nodes. Specifically, when a given direction of the end to end path of an optical circuit will use a single wavelength, then a single end to end wavelength is provisioned for that direction (the source and destination nodes of that wavelength are access nodes of the optical network and are the same as the end nodes of the optical circuit). However, in the case where a single wavelength for a given direction will not be used, wavelength conversion is necessary and a lightpath with two or more wavelengths is provisioned for that direction of the end to end path of the optical circuit.
Put another way, the optical network can be thought of as consisting of the logical pairing of lightpaths to construct bi-directional associations between the access nodes providing ingress to and egress from the optical networks. In GMPLS terminology, each lightpath can be considered to be a uni-directional Label Switched path (LSP) and their pairing as optical circuits to be a Bi-Directional LSP. Each of these LSPs (uni-directional or bi-directional) forms an end to end path where the generalized label(s) are the wavelength(s) of the lightpath(s) used. When wavelength conversion is not used for a given bi-directional LSP, there will be a single conversion free, end to end lightpath in each direction (and thus, a single wavelength; and thus, a single generalized label).
The term disjoint path is used to describe a relationship between a given path and certain other network resources (e.g., nodes, links, etc.) wherein there is no sharing of network resources between the path taken by the optical circuit and the other network resources that were specified. For example, two optical circuits are said to be “fully link disjoint” if they do not pass along any of the same links. Similarly, two optical circuits are said to be ‘fully node disjoint’ if this do not pass through the same two nodes (except for the ingress and egress nodes). Note that it is possible to be “fully link disjoint” without being “fully node disjoint”. There are various levels of disjointness (e.g., maximally link disjoint, fully link disjoint, maximally node disjoint, and fully node disjoint; and each can additionally be shared risk group (SRG) disjoint). For instance, a first and second path are disjoint if the network resources they use meet the required level of disjointness.
Disjoint paths are formed for a variety of reasons, including to form “restricted paths” and “protection paths”. “Restricted paths” are light paths that have administrative restrictions placed on the specific links and/or nodes that they are allowed to traverse. For example, a path may be required to pass through a specific link or, alternatively, not to pass-though a particular node. Protection paths are used to provide physical redundancy; that is, they are used as alternate paths to working paths in case of a network failure of some kind. If the working path and the protection path are not disjoint and hence share one or more network resources, then in the event of a failure of that shared resource, neither the working nor the protect traffic can be transmitted between ingress and egress nodes. For this reason, it is desired, or even required, that the protection path be fully link and node disjoint from the working path. Protection paths are commonly implemented as either: 1) 1+1 protected; 2) 1:1 protected; or 3) 1:N protected. A 1+1 or 1:1 protected path is a disjoint path from node A to node B in the network where one of the paths is a working path, and the other is a protection path. The working path and the protection path are typically established at the same time. In the case of a 1+1 protected path, the same traffic is carried on both paths, and the receiving node selects the best of the paths (i.e., if the one currently selected by the receiving node degrades or fails, that node will switch to the other). In contrast, in the case of a 1:1 protected path, traffic is transmitted on the working path; when a failure occurs on the working path, traffic is switched to the protection path. In 1:N protection, multiple disjoint working paths share the same protection path.
An optical network device can be thought of comprising 2 planes: a data plane and a control plane. The data plane includes those optical components through which the light travels (e.g., the switch fabric; the input and output ports; amplifiers; wavelength multiplexers; optical splitters; etc.), and components that convert electrical signals into light (e.g. a laser) as well as those that convert light into electrical signals (e.g. a photodetector). The control plane includes those components that control the components of the data plane. For instance, the control plane is often made up software executing on a set of one or more microprocessors inside the optical network device which control the components of the data plane. To provide a specific example, the software executing on the microprocessor(s) may determine that a change in the switch fabric is necessary, and then instruct the appropriate optical components(s) to cause that action to occur. It should also be noted that the control plane of an optical network device is in communication with a centralized network management server and/or the control planes of one or more other network devices.
A number of different network topologies have been developed for optical network devices, including ring and meshed based topologies. Similarly, a number of different control planes and data planes implementations have been developed for optical network devices. For instance, various different technologies have been used to physically realize the switch fabric that the data (optical signals) gets re-directed to, including Micro-Electro-Mechanical Systems (MEMS), acousto-optics, planar waveguide, holographic, and optical phased array switch fabrics.
There are generally three approaches to operating an optical network: 1) centralized provisioning; 2) source based provisioning; and 3) hybrid provisioning. In centralized provisioning, a centralized network management server communicates with each of the optical network devices of a network and maintains a network database. In response to a demand request for an optical circuit, the network management server calculates lightpaths for the demand that meets both administrative and network performance requirements. The network management server then causes the allocation of the lightpaths and the configuring of the switch fabrics at all the network nodes along the lightpaths necessary to realize the establishment of that optical circuit.
In source based provisioning, each of the access nodes of the network performs the work of building/maintaining a network database (e.g., using OSPT-TE). In response to a demand for an optical circuit received by an access node, that node: 1) itself finds the shortest lightpaths; and 2) signals to each of the other nodes in the path to allocate resources to the requested lightpath. In response, each node will itself allocate resources (if it is still able to meet the request) and initiate any action required to ensure the proper connectivity for the lightpaths within itself
In hybrid provisioning, each of the nodes of the network exchanges messages containing information relating to connectivity status of links directly connected to themselves, for example using OSPF link state advertisements to build network databases, and uses these messages to build network database and maintained in a centralized network management server. In response to a demand from a requesting entity, the network management server initiates ‘third party’ source based provisioning (i.e. the centralized server initiates the call set-up request on behalf of the ‘originating node’). The call-set up subsequently proceeds as in the case of source-based provisioning.
Regardless of the approach used, operating an optical network typically requires: A) building and maintaining network databases; and B) establishing lightpaths. For example, the network databases can include: 1) link state databases that track resource usage and availability information (e.g., the link(s), lambda(s), etc.) regarding adjacent optical nodes (e.g., using a link management protocol (LMP)); and 2) topology databases that track information (e.g., nodes, links, lambdas, etc.) for the physical connectivity of the nodes in a domain and/or the entire network (e.g., using OSPF-TE). In order to establish an LSP, the following operations are typically performed: 1) determining a shortest path/wavelength between the source and destination; 2) allocate that path/wavelength within its own node; 3) affecting the connectivity required in its own node; and 4) requesting (aka ‘signaling’) each of the other nodes in the calculated path to allocate and affect resources within themselves).
Generally, link state routing protocols such as OSPF and OSPF-TE operate by performing periodic link state advertisements (LSAs) to maintain a routing table that includes reachability information for each destination in the network. Within each period: every node in the network floods its link state information to other nodes in the network; this link state information is stored by every node; every node processes this information and builds a network map (this network map is also later on spread around to decrease processing); each node reduces these network maps to graph structures (adding redundant/dummy nodes to cover multiple channels on an optical link—thus, the graph separately represents the path/wavelength combinations on a given physical link as separate links); each node uses its graph structures as an input to a shortest path first algorithm (e.g., Dijkstra's algorithm, BFS algorithm, etc.) to form a shortest path first tree (which is actually a shortest path/wavelength combination first tree) that stores the shortest path/wavelength combination to each destination; and each node uses its shortest path first tree to update its maintained routing table. In addition, the graph structures may also be used as an input to a disjoint shortest path first algorithm (e.g., Vertex splitting Method1 algorithm, vertex splitting Method2 algorithm, Surballes Algorithm (for calculation of edge disjoint paths), etc.) that relies on applying a shortest path first algorithm to the graph structure. (see Bhandari, Ramesh. Survivable Networks Algorithms for Diverse Routing, Kluwer Academic Publishers (1999). The results of such a disjoint shortest path first algorithm are used to install an alternative next hop for a destination in the routing table. Ultimately, the routing table is maintained period to period and stores the “next hop” for each possible destination (i.e. the physical interface to be used to reach each destination). It does not store the path/wavelength combinations. This is also true for the OSPF-TE extension of OSPF. One difference between OSPF and OSPF-TE is the data that is carried by the LSAs. For example, the channel information present on a link can be embedded inside the LSAs for OSPF processing engine to be able to use channel information to finally obtain shortest path/wavelength combination.
One problem with the above approach is the relatively high computational intensity; especially in WDM optical networks. For example, a typical optical network having 10 nodes, each with 8 optical fibers capable of carrying 40 channels going out, results in 320 channels per node. In addition, as indicated above, the redundant/dummy nodes are added to represent multiple channels on each physical link, so each channel is associated with a separate node data structure so that it is represented as a separate link (that is, every path/wavelength combination on a physical link is represented in the graph as if it were a separate physical link). As such, the graph structure stores every node with degree 320 to represent a network having 3200 links. Each of these relatively large graph structures are then operated on: 1) by a shortest path first algorithm to select path/wavelength combinations from the resulting shortest path/wavelength combination first tree; and/or 2) by a disjoint shortest path first algorithm to select path/wavelength combinations from the result.
Methods to address the relatively large computational complexity of OSPF include: 1) pre-emption of Djikstra's algorithm during periodic route computation (after the algorithm has run for a certain maximum amount of time, it is stopped and the search context is saved; if a route miss occurs between the stopped time and the next update/refresh then the search is continued); and; 2) figuring out disjoint areas within an OSPF area based on the interfaces connecting to a router (when an update occurs, only the affected sub-area routes are re-computed).
Another problem with existing optical networks is the network databases used and the manner in which they are built and maintained. Specifically, these monolithic physical topology databases (e.g., built with OSPF or OSPF-TE) are very large because they must store all of the data to give a physical view of the network (not only connectivity at the link level, but connectivity at the lambda level because there are multiple lambdas per link and because different lambdas on a given link may provide different bit rates; etc.). These large network databases are relatively time consuming to parse and require a relatively long time and a relatively large amount of node intercommunication to propagate changes.